/**
 * 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

 

示例 1：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3
解释：节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2：


输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5
解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3：

输入：root = [1,2], p = 1, q = 2
输出：1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

/**
思路
对于根节点 root，p、q 的分布，有两种可能：

p、q 分居 root 的左右子树，则 LCA 为 root。
p、q 存在于 root 的同一侧子树中，就变成规模小一点的相同问题。
定义递归函数
递归函数：返回当前子树中 p 和 q 的 LCA。如果没有 LCA，就返回 null。

从根节点 root 开始往下递归遍历……

如果遍历到 p 或 q，比方说 p，则 LCA 要么是当前的 p（q 在 p 的子树中），要么是 p 之上的节点（q 不在 p 的子树中），不可能是 p 之下的节点，不用继续往下走，返回当前的 p。

当遍历到 null 节点，空树不存在 p 和 q，没有 LCA，返回 null。

当遍历的节点 root 不是 p 或 q 或 null，则递归搜寻 root 的左右子树：

如果左右子树的递归都有结果，说明 p 和 q 分居 root 的左右子树，返回 root。
如果只是一个子树递归调用有结果，说明 p 和 q 都在这个子树，返回该子树递归结果。
如果两个子树递归结果都为 null，说明 p 和 q 都不在这俩子树中，返回 null。

作者：xiao_ben_zhu
链接：https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/solution/jsersi-lu-hao-li-jie-by-hyj8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

 */

var lowestCommonAncestor = function (root, p, q) {

    if (!root) return null

    if (root === p || root === q) {
        //遇到q 或者 p 直接返回当前节点
        return root
    }
    //递归左右子树
    const left = lowestCommonAncestor(root.left, p, q)
    const right = lowestCommonAncestor(root.right, p, q)

    //根据递归的结果返回谁是LCA
    if (left && right) {
        return root
    }
    //有左返左，有右返右
    return left || right
}



// 使用map记录root的节点

var lowestCommonAncestor = function (root, p, q) {
    let visited; let parent;
    visited = new Set();
    parent = new Map();
    dfs(root);
    while (p != null) {
        visited.add(p.val);
        p = parent.get(p.val);
    }
    while (q != null) {
        if (visited.has(q.val)) {
            return q;
        }
        q = parent.get(q.val);
    }
    return null;
};
function dfs(root) {
    if (root.left != null) {
        parent.set(root.left.val, root);
        dfs(root.left);
    }
    if (root.right != null) {
        parent.set(root.right.val, root);
        dfs(root.right);
    }
}